\documentclass{article}

\usepackage{xltxtra}
\usepackage{listings}
\usepackage{fontspec}
\setmainfont{WenQuanYi Zen Hei Mono}
\usepackage{geometry}
\geometry{left=2cm,right=6cm,top=2cm,bottom=2cm}

\begin{document}

\title{设计思路及测试说明}
\author{3220100159 梁越}
\date{\today}

\maketitle

\section{设计思路}
每种硬币的最大数量和要达到的金额都由输入决定。\\
但如果要计算很多金额的最小硬币数，\\
每个都像这样计算显然会有很多重复的计算，\\
如果我们创建一个备忘录来记录已经计算过的金额的最小硬币数\\
那么就可以直接调用而不需要重复计算。\\
每选择一个硬币，就剩下n-coins[j]的金额来计算，\\
以此作为子问题，不断递归。\\
整理一下，需要\\
一个数组来记录已经计算过的金额，\\
一个数组储存硬币的四种面值，\\
一个面值与最大数量一一对应的数组来控制计算次数，\\
一个总金额。\\
函数coin接受以下几个参数：\\
1.硬币面值的数组\\
2.硬币最大数量\\
3.需要凑出的金额\\
并返回金额的最小硬币数\\
创建dp数组，将其每个元素值都初始化为amount+1;\\
定义函数dp来计算给出金额的最小硬币数\\
对于每种硬币，与n-coin金额所需的最小硬币数比较\\
不断循环\\
最终可以得到n所需的最小硬币数。\\
同时要更新剩余可用的硬币数。\\
若最终结果不是初始值，则说明找到了最小硬币数，返回即可\\
反之说明无法凑出要求金额，返回-1。\\
在测试时，\\
首先让用户输入各种面值硬币的最大数量，\\
其次输入金额，调用头文件里的该函数，计算出最小硬币数。\\
在实现时遇到了困难\\
因为我们的硬币数目是受到限制的\\
所以应有一个变量随着i的不断变化而变化\\
引入一个数组cause来记录是哪枚硬币引起的变化\\
那么该表如下\\
i      1 2 3 4 5 6 7 8 9 10 11 20\\
cause  1 1 1 1 5 1 1 1 1 10 1  10\\
理想状态是当dp更新后\\
只有相关的硬币数额减少\\
当引起i和i-coins[j]的原因相同时\\
说明到这一步中间硬币面额没有发生改变\\
消耗的仍为同一面额硬币\\
在原来基础上减一表示消耗\\
即形如7,8等，应令j的数额-1\\
反之说明，上一级的硬币消耗以被更大面额的硬币覆盖\\
应恢复至初始值\\
\section{声明}
参考了https://leetcode.cn/problems/coin-change/solutions/132979/322-ling-qian-dui-huan-by-leetcode-solution/的逻辑

\section{测试说明}
大体思路是输入可以凑出的金额和对应的数量，看输出\\
输入凑不出的金额和对应数量，看输出\\
输入：0,0,0,0,5\\
输出：-1\\
输入：10,10,10,10,29\\
输出：5\\
输入：10,10,10,10,123\\
输出：9\\
输入：5，0，0，0，6\\
输出：-1\\
输入：2，2，0，1，12\\
输出：4\\
\end{document}
